package com.uyong.study.datastruct;

/**
 * 堆<p>堆是一个完全二叉树，可以用数组来实现</p>
 * 
 * @author gonggy
 * @since 2019-02-19
 */
public class Heap {

	private int[] datas; // 数组，从下标1开始存放数据
	private int capacity; // 数组容量
	private int count; // 实际存储的数据个数

	public Heap(int capacity) {
		this.capacity = capacity;
		datas = new int[capacity];
		count = 0;
	}

	/**
	 * 插入，时间复杂度O(logn)
	 * 
	 * @param data
	 */
	public void insert(int data) {
		// 堆满了
		if (count >= capacity) {
			return;
		}

		count++; // 先加1，确保数组从1开始存储数据

		// 插入堆的最后
		datas[count] = data;

		// 调整堆，使其满足第二个条件
		int index = count;
		while ((index / 2 > 0) && datas[index] > datas[index / 2]) {
			swap(datas, index, index / 2);
			index = index / 2;
		}
	}

	/**
	 * 删除堆顶元素,时间复杂度O(logn)
	 */
	public void deleteTop() {
		if (count == 0) {
			return;
		}

		// 用最后一个元素替换堆顶元素
		datas[1] = datas[count];

		count--;

		// 调整堆，使其满足第二个条件
		heapify(datas, count, 1);
	}

	/**
	 * 自上向下堆化，时间复杂度O(logn)
	 * 
	 * @param datas 数组
	 * @param count 数组实际存储的数据个数
	 * @param index
	 */
	private static void heapify(int[] datas, int count, int index) {
		int maxIndex;
		while (true) {
			maxIndex = index;
			if (index * 2 <= count && datas[index * 2] > datas[index]) {
				maxIndex = index * 2;
			}
			if (index * 2 + 1 <= count && datas[index * 2 + 1] > datas[maxIndex]) {
				maxIndex = index * 2 + 1;
			}
			if (maxIndex == index) {
				break;
			}
			swap(datas, maxIndex, index);

			index = maxIndex;
		}
	}

	/**
	 * 堆排序，时间复杂度O(nlogn)
	 * 
	 * @param data  数组，下标从1开始
	 * @param count 数组中时间的数据个数
	 */
	public static void sort(int[] data, int count) {
		buildHeap(data, count);
		int k = count;
		while (k > 1) {
			swap(data, 1, k);
			--k;
			heapify(data, k, 1);
		}
	}

	/**
	 * 建堆
	 * 
	 * @param data
	 * @param count
	 */
	private static void buildHeap(int[] data, int count) {
		for (int i = count / 2; i >= 1; i--) {
			heapify(data, count, i);
		}
	}

	private static void swap(int[] data, int first, int second) {
		int tmp = data[first];
		data[first] = data[second];
		data[second] = tmp;
	}

	public int[] getDatas() {
		int[] result = new int[count];
		System.arraycopy(datas, 1, result, 0, count);
		return result;
	}

	public int getCapacity() {
		return capacity;
	}

	public int getCount() {
		return count;
	}
}
